public class GasStation {
    /**
     * 在一条环路上有 n个加油站，其中第 i个加油站有汽油gas[i]升。
     * 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1个加油站需要消耗汽油cost[i]升。你从其中的一个加油站出发，开始时油箱为空。
     * 给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
     * 链接：https://leetcode-cn.com/problems/gas-station
     * @param gas
     * @param cost
     * @return
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int i=0;
        while (i<n){
            int sum_gas = 0;
            int sum_cost =0;
            int cnt =0;
            while (cnt<n){
                int j = (i+cnt)%n;
                sum_gas += gas[j];
                sum_cost += cost[j];
                if (sum_gas<sum_cost){
                    break;
                }
                cnt++;
            }
            if (cnt==n){
                return i;
            }else {
                i = i+cnt+1;
            }
        }
        return -1;

    }
}
